本篇內容

• 介紹Yacc的規則匹配
  • Shift
  • Reduce

Yacc的規則匹配

經過昨天的實作後，我們建立了加減乘除四個規則，讓計算機可以做兩個正整數的四則運算了。
然而，當規則變多之後，Yacc是怎麼進行處理，讓字串組合匹配到正確的規則呢?

今天，我們便來看看Yacc是如何一步步進行規則匹配的。

在Yacc裡面會有一個空的暫存器(buffer)，資料結構為stack，用來放文本所產生的token。
接下來，Yacc會進行兩個主要操作："Shift" 和 "Reduce”

Shift（移位操作）：

• "Shift" 是指將輸入中的一個終端符號（token）移到buffer中的動作。
• 當Parser遇到一個終端符號，它將該符號從input中讀取並將其推入buffer stack。
• "Shift" 操作表示parser正在構建語法樹的一部分，將token視為尚未處理的一部分。
• 通常，在確定當前輸入符號應該處理的上下文後，解析器執行 "Shift" 操作。

Reduce（歸納操作）：

• "Reduce" 是指將buffer內的一個或多個符號（通常是非終端符號）替換為一個非終端符號的動作。
• 當parser識別到一個或多個已經匹配的規則（例如，語法規則中，冒號右方的部分），它將相應的符號從buffer stack中移除，然後將相應的非終端符號壓入buffer stack。
• "Reduce" 操作表示解析器已經識別並處理了輸入中的一個語法結構，並用非終端符號表示該結構。
• 通常，"Reduce" 操作發生在buffer stack上有一個或多個特定符號時，可以根據語法規則將它們替換為一個非終端符號。

我們來看看以下的例子吧！

以下是Yacc的語法規則：

func: 
      VAR '=' expr    { printf("%s = %d", $1, $3); }
    ;    
expr:
      NUMBER '+' NUMBER   { $$ = $1 + $3; }
    | NUMBER '-' NUMBER   { $$ = $1 - $3; }
    | NUMBER '*' NUMBER   { $$ = $1 * $3; }
    | NUMBER '/' NUMBER   { $$ = $1 / $3; }
    ;

接著，我們給Parser輸入一個文本：

X = 3 + 2

經過lex的token標記後，會變成這樣：

VAR '=' NUMBER '+' NUMBER

至此， Yacc便開始進行規則匹配了。

1. 由於目前buffer內沒東西，所以shift第一個token VAR

   VAR
   

2. 由於沒有匹配到對應的規則，所以繼續shift第二個token '='

   VAR '='
   

3. 由於還是沒有匹配到對應的規則，所以繼續shift第三個token NUMBER

   VAR '=' NUMBER
   

4. 由於還是沒有匹配到對應的規則，所以繼續shift第四個token '+'

   VAR '=' NUMBER '+'
   

5. 由於還是沒有匹配到對應的規則，所以繼續shift第五個token NUMBER

   VAR '=' NUMBER '+' NUMBER
   

6. 此時，序列”NUMBER '+' NUMBER”可以匹配到規則”expr”，因此進行reduce
   首先，先將匹配的字串組從stack中移出。
   進行化簡後，得到一個非終端符號expr，並進行對應的操作(計算 3+2=5，然後存在變數expr中)
   最後，將expr放回buffer內

   VAR '=' expr
   

7. 此時，序列”VAR '+' expr”可以匹配到規則”func”，因此進行reduce
   首先，先將匹配的字串組從stack中移出。
   進行化簡後，得到一個非終端符號func，並進行對應的操作(印出結果文字: X = 5)
   最後，將func放回buffer內

   func
   

最終，buffer中只剩下一個 "func"，它代表整個語法樹的根。我們便完成了整個文本的規則匹配。

結語

我們今天終於了解Yacc是怎麼做規則匹配的。如此一來，再複雜字串組結構都能藉由一步步化簡，最終匹配到規則並進行相對應的操作。

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
• Tom Niemann. Lex & Yacc